#define _CRT_SECURE_NO_WARNINGS
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    struct cmp
    {
        bool operator()(ListNode* l1, ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
        ListNode* head = new ListNode;
        ListNode* tmp = head;
        for (int i = 0; i < lists.size(); i++)
            if (lists[i]) pq.push(lists[i]);

        while (!pq.empty())
        {
            ListNode* top = pq.top();
            pq.pop();
            if (top->next)
                pq.push(top->next);
            tmp->next = top;
            tmp = tmp->next;
        }
        tmp = head->next;
        delete head;
        return tmp;
    }
};